Simply stated, a schedule informs a party of what activity/activities are to take place, when the activity/activities will take place, and who will perform the activity/activities. A schedule may run for an hour, day, week, month, or other interval of time. Generally, the “when” quality is a specific reference to start an activity at a specific time and/or end that activity at a later specific time.
With respect to the “what” quality, a schedule may provide very generic activity information such as sleeping, eating, building, or some other activity. The “what” quality may also provide resource information—sleeping in bed 2, eating at table 5, or building at station 4.
With respect to the “who” quality—a schedule may provide information to observers of an activity regarding who is performing the activity, or the schedule may provide direction to a party to commence with or finish an activity. Typically, a schedule will also indicate free time, as in unscheduled time, as well as the busy time, as in time currently scheduled for activities.
A schedule may be assembled by scheduling activities in the order in which they are received, or in which they logically occur. A schedule may also be assembled by prioritizing activities in descending or ascending order of preference. Where the time that an activity is to occur or might occur is important, the focus of placement may shift from simple order of preference to level of priority at a specified time.
In many real world settings there are specific demands upon schedules. For any given resources (such as an aircraft, a satellite or a computer) there may be a finite availability both in terms of how long something may occur and how much may occur. Computer speeds are continuing to increase, but for each second of time a computer (CPU) has a finite number of operations to perform. A more powerful CPU resource may indeed execute more operations than a less powerful CPU resource, and such an option may or may not be taken into account when forming a schedule. In another example, an aircraft or satellite may not be over a particular spot on the earth at all times, and even when over a target area, may only be able to observe, deploy, gather, or perform a finite number of activities before returning to base or passing out of range.
To fill a schedule with activities competing for time slots, or to enter new activities into an existing schedule where the new activities compete with existing scheduled activities is far from easy. Many problems, and the algorithms that may be applied to them, are linear—double or triple the input and they will take twice or three times as long to complete. Others may be quadratic, cubic or another polynomial. When a class of problems is encountered where the solution is not polynomial, it may well be a nondeterministic polynomial—more commonly referred to as “NP-hard”.
Filling a schedule and inserting new activities into a schedule are activities that qualify as NP-hard. NP-hard problems are well known and frequently encountered, yet no algorithm to solve them to optimality in polynomial time is known. A fast algorithm is one that will return the best solution quickly enough for the solution to actually be useful. If the solution takes years to compute, it is quite likely that the term of usefulness will have long expired.
A famous example of such an NP-hard problem is the Traveling Salesman. A salesman desires to visit each state capital and wants to minimize his or her driving time. Within the 50 states there are 49! possible choices—and no algorithm is known to exist that will solve this problem in a reasonable amount of time.
For a schedule, it may be that, given an infinite amount of time, a best solution may be found. However, during the instantiation of a schedule, and the subsequent modification of a schedule, real time continues to progress. As a result, by the time a best solution has been found, it is entirely possible that too much time will have passed and the issue will be moot.
In many instances, scheduling algorithms are designed on a case by case basis to address what is perceived as a specific scheduling need. Although effective, this can lead to significant inefficiency as many scheduling systems may utilize similar if not identical operations. In addition, if an issue of priority effecting one or more tasks changes suddenly due to a real world crisis, a customized algorithm may be unable to favorably adapt.
Indeed there are many different types of scheduling methodologies, and even for the same type of event scheduling, different methodologies may be more or less favored at different times.
Where the desire is to schedule the maximum number of activities, regardless of priority, an English Auction may be quite effective. However, if there is a premium placed on the scheduling of higher priority activities, then an English Auction may not offer the best solution. Indeed, if the mandate is to schedule as many events as possible, but no higher priority activity may ever be usurped by one or more lower priorities, then the English Auction approach will not be acceptable. And again, though an English Auction method may be appropriate for some tasks in a scheduling problem it may not be the most desirable method for all tasks in the scheduling problem.
Mixed Integer methods have also been proposed to provide schedule modification. In a Mixed Integer method, however, each and every allowable possible permutation of activities is considered and evaluated. Even with the speed of modern computers, the focus upon trying all permutations for comparison makes Mixed Integer methods vastly impractical for large scale scheduling problems, but may be ideal for small, time insensitive problems.
Further a system designed to effectively process on-demand tasking may not be ideal for scheduling and rescheduling a list of standing or repeated tasks known to occur at some point beyond the immediate here and now.
Hence, there is a need for a task scheduling method that overcomes one or more of the technical problems found in existing scheduling systems.